There are several methods available for digital data resolution conversion. Popular methods are transform domain methods such as the fractional Fourier transform (fractional FFT or Chirp-Z transform), the discrete cosine transform (DCT), and discrete wavelet transform (DWT). In addition, there are a number of spatial domain methods such as re-sampling and digital filtering with finite-impulse response (FIR) and infinite-impulse response (IIR) filters and interpolation with continuous, usually cubic, splines. When a continuous kernel produces data that passes through original data points, it is often called an interpolating kernel. When the interpolated data produced is not constrained to pass through the original data points, it is often called an approximating kernel. There are a number of constraints that must be met in the design of these continuous kernels.
Commonly used continuous kernels for interpolation are the nearest neighbor (NN), linear, quadratic, and cubic kernels. The NN kernel is the simplest method of interpolation, which interpolates the image with the pixel value that is spatially nearest to the required one. This method works quite well when the scaling ratio is an integer multiple of the original data as it introduces no new values (i.e., no new colors) and preserves sharp edges. However, at other ratios the NN kernel has the disadvantage of shifting edge locations which often produces visible distortions in the output image, especially in images containing text or fine line details. Linear interpolation on the other hand allows for the introduction of new grey levels (or colors) that are effectively used to position edges at sub-pixel locations. This has the advantage of reducing the effect of shifted edge locations, however sharp edges can appear to be blurred. Quadratic and cubic interpolation provide steeper step responses and therefore less edge blurring, however, the steeper response results in an overshoot on either side of the edge. These overshoots can make the edges in natural images appear sharper, but on text, fine lines, or on other computer generated graphics these overshoots are clearly visible and detract from the perceived image quality and text legibility.
From the above, it can be concluded that each kernel has its own strengths and weaknesses. Further, there are certain image areas which are best interpolated using kernels of different shapes. Simply applying a single continuous convolution kernel at every image pixel will not satisfy all of the requirements for a general-purpose resolution conversion application.
One known method of generating a kernel with both a steep step response, but no overshoot is to adjust the parameters of the cubic kernel according to image information so as to remove the overshoot in the step response. The two-parameter Catmull-Rom cubic has a kernel of the form:
                              h          ⁡                      (            s            )                          =                                  ⁢                  {                                                                                                                                        (                                                  2                          -                                                                                    3                              2                                                        ⁢                            b                                                    -                          c                                                )                                            ⁢                                                                                                  s                                                                          3                                                              +                                                                  (                                                                              -                            3                                                    +                                                      2                            ⁢                            b                                                    +                          c                                                )                                            ⁢                                                                                                  s                                                                          2                                                              +                                          (                                              1                        -                                                                              1                            3                                                    ⁢                          b                                                                    )                                                        ,                                                                                                                      s                                                        ≤                  1                                                                                                                                                                        (                                                                                                            -                                                              1                                6                                                                                      ⁢                            b                                                    -                          c                                                )                                            ⁢                                                                                                  s                                                                          3                                                              +                                                                  (                                                  b                          +                                                      5                            ⁢                            c                                                                          )                                            ⁢                                                                                                  s                                                                          2                                                              +                                                                  (                                                                                                            -                              2                                                        ⁢                            b                                                    -                                                      8                            ⁢                            c                                                                          )                                            ⁢                                                                      s                                                                                      +                                          (                                                                                                    4                            3                                                    ⁢                          b                                                +                                                  4                          ⁢                          c                                                                    )                                                        ,                                                                              1                  <                                                          s                                                        ≤                  2                                                                                                      0                  ,                                                            Otherwise                                                                        (        1        )            
Popular choices for the parameters b and c are (b=0, c=0.5), which is the interpolating cubic that agrees with the first three terms of the Taylor series expansion of the original image, and (b=1, c=0) which is the approximating cubic B-sp line. One known method fixes the parameter b at b=0, whilst c is varied between 0, 0.5, and 1 dependent upon the edge strength measured using a Laplacian of Gaussian (LOG) edge detector. At a sharp edge c=0 the resulting cubic is:
                                              ⁢                              h            ⁡                          (              s              )                                =                      {                                                                                                                                                        2                          ⁢                                                                                                                  s                                                                                      3                                                                          -                                                  3                          ⁢                                                                                                                  s                                                                                      2                                                                          +                        1                                            ,                                                                                                                                  0                      ,                                                                                  ⁢                                                                                                                                          s                                                                    ≤                      1                                                                                                            Otherwise                                                                                                          (        2        )            
There is however, a problem with using this kernel to interpolate image data when the re-sampled pixel displacement is not significantly different from the original pixel displacement, say a re-sampling ratio of 10/11 or 11/10. In this instance pixels at the edges of text and other fine lines take on a grey value rather than the original black or white values. This again results in the blurring of sharp edges and a reduction in the observed image quality.
A further problem with the conventional continuous convolution kernel is associated with its application to edges at oblique orientations in the image plane. The conventional kernels can be either applied in separable fashion, ie., first to the rows of the image and then to the columns, or applied in a 2-dimensional form where they are directly convolved with the 2-dimensional image data. However, their orientations in these implementations are limited to either: horizontal, vertical, or symmetrical. Upon encountering an oblique edge, the pixels on either side of the edge are primarily used in the interpolation rather than pixels along the edge. This results in an interpolated edge that no longer appears to be clean and smooth, but appears to be jagged, or blurred, or both. A solution to the above problem is known whereby interpolation across edges is prevented by using extrapolated estimates of pixel values for pixels on the other side of the edge in the bilinear interpolation. However, this method requires highly accurate sub-pixel edge estimation at the output resolution and iterative post-processing using a successive approximation procedure. Both of the above-described methods place high demands on memory and processing resources. Another approach to the problem is to utilise a set of 2-dimensional “steerable” kernels that can be oriented along the line of an edge during image interpolation. In this way the method smooths along the edge line (to reduce edge jaggedness), but not across the edge (so preserving edge sharpness).
A method of selecting interpolation kernels based on edge strength, or user input in known. However, there are some defects that prevent this method from working optimally. Firstly, the use of edge strength alone as the basis for kernel selection does not provide sufficient information for reliable kernel selection (especially at oblique edges). Secondly, kernel selection based solely upon user input is impractical and does not specify the kernel selection in enough detail. For the example, in the sub-image shown in FIG. 7(a), there is not one single kernel that is ideal for the whole sub-image. In general, different kernels are required at a resolution that is impractical to be specified by a user.
It is an object of the present invention to ameliorate one or more disadvantages of the prior art.